"""
Problem 63: https://projecteuler.net/problem=63

The 5-digit number, 16807=7^5, is also a fifth power. Similarly, the 9-digit number,
134217728=8^9, is a ninth power.
How many n-digit positive integers exist which are also an nth power?
"""

# _*_ conding:UTF-8 _*_
'''
@author = Kuperain
@email = kuperain@aliyun.com
@IDE = VSCODE Python3.8.3
@creat_time = 2022/5/19
'''


def solution() -> int:
    '''
    10^(k-1) <= n^k < 10^k
    so, (10/n)^k <= 10, n<10

    10^(1 - 1/k) <= n < 10
    '''
    k = 1
    while 10**(1 - 1/k) <= 9:
        k += 1
    # k=22, 10**(1-1/22) = 9.006280202112785, do not exist such n

    return sum([9 - int(10**(1 - 1/i)) for i in range(2, k)])+18
    # 18 means i^0, i^1, i = 1,2,3...9


if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose=False)

    print(solution())
    # 58
